// https://www.lintcode.com/problem/recommended-results-are-scattered/

public class Solution {
    /**
     * @param elements: A list of recommended elements.
     * @param n: [picture P] can appear at most 1 in every n
     * @return: Return the scattered result.
     */
    public List<String> scatter(List<String> elements, int n) {
        // write your code here
        // 两个游标记录P/V位置即可
        List<String> ret = new ArrayList<>();
        int start = 0;
        while (true) {
            String elem = elements.get(start);
            if (elem.charAt(0) == 'P') {
                ret.add(elem);
                break;
            }
            ret.add(elem);
            ++start;
        }
        int size = elements.size();
        int vstart = start + 1, pstart = start + 1;
        while (true) {
            // 先n - 1个V
            int vs = 0;
            while ((vstart < size) && (vs < (n - 1))) {
                String elem = elements.get(vstart);
                if (elem.charAt(0) == 'V') {
                    ret.add(elem);
                    ++vs;
                }
                ++vstart;
            }
            if (vs != (n - 1)) {
                break;
            }
            // P
            while (pstart < size) {
                String elem = elements.get(pstart);
                if (elem.charAt(0) == 'P') {
                    ret.add(elem);
                    ++pstart;
                    break;
                }
                ++pstart;
            }
            if (pstart >= size) {
                break;
            }
        }
        return ret;
    }
}